#include <cstdio>

#define INF 0x3F3F3F3F

int map[3][4];
bool book[10];
int cnt;

int dfs(int m) {
	if (m<=2) {
		int t = m+1;
		for (int i=0; i<=9; i++) {
			if (book[i]) continue;
			if (i-map[0][t-1]!=1 && i-map[0][t-1]!=-1) {
				map[0][t] = i;
				book[i] = true;
				dfs(m+1);
				book[i] = false;
				map[0][t] = INF;
			}
		}
	} else if (m<=6) {
		int t = m-3;
		for (int i=0; i<=9; i++) {
			if (book[i]) continue;
			if (t-1>=0 && ((i-map[1][t-1]==1 || i-map[1][t-1]==-1) || 
				i-map[0][t-1]==1 || i-map[0][t-1]==-1)) continue;
			if (i-map[0][t]==1 || i-map[0][t]==-1) continue;
			if (t+1<=3 && (i-map[0][t+1]==1 || i-map[0][t+1]==-1)) continue;
			map[1][t] = i;
			book[i] = true;
			dfs(m+1);
			book[i] = false;
			map[1][t] = INF;
		}
	} else if (m<=9) {
		int t = m-7;
		for (int i=0; i<=9; i++) {
			if (book[i]) continue;
			if (t-1>=0 && ((i-map[2][t-1]==1 || i-map[2][t-1]==-1) || 
				i-map[1][t-1]==1 || i-map[1][t-1]==-1)) continue;
			if (i-map[1][t]==1 || i-map[1][t]==-1) continue;
			if (t+1<=3 && (i-map[1][t+1]==1 || i-map[1][t+1]==-1)) continue;
			map[2][t] = i;
			book[i] = true;
			dfs(m+1);
			book[i] = false;
			map[2][t] = INF;
		}
	} else {
		//printf("BINGO!!!\n");
		cnt++;
	}
}

int main() {
	map[0][0] = INF;
	dfs(0);
	printf("\n\ncnt=%d\n", cnt);
	return 0;
}
